package sort;

public class MyMergeSort {

	public static void main(String[] args) {
		int[] a = { 7, 6, 2, 15, 1, 3, 5, 11, 10, 2, 18, 9, 10, 19, 23, 20, 26,
				54, 34 };
		mergeSort(a);
		// merge(a, 2, 4, 9);
		for (int i : a) {
			System.out.print(i + " ");
		}
	}

	public static void mergeSort(int[] a) {
		if (a == null || a.length == 0) {
			return;
		}
		int len = 1;
		// len表示归并的长度，首先是1，之后是2,4...
		while (len <= a.length) {
			for (int i = 0; i + len < a.length; i += len * 2) {
				int low = i, mid = i + len - 1, high = i + 2 * len - 1;
				// 注意high不能超过长度
				if (high > a.length - 1) {
					high = a.length - 1;
				}
				merge(a, low, mid, high);
			}
			len *= 2;
		}

	}

	// 将数组a中的元素使用归并的方式排序
	public static void merge(int[] a, int low, int mid, int high) {
		// 新建一个数组来保存排序后的结果
		int[] temp = new int[high - low + 1];
		int k = 0;
		for (int i = low, j = mid + 1; k < high - low + 1;) {
			// 当一个数组全加入以后
			if (i == mid + 1 && j <= high) {
				temp[k++] = a[j++];
				continue;
			}
			if (j == high + 1 && i <= mid) {
				temp[k++] = a[i++];
				continue;
			}
			// 都没有全部加入
			temp[k++] = a[i] < a[j] ? a[i++] : a[j++];
		}
		// 重新赋值
		for (int i = 0; i < temp.length; i++) {
			a[i + low] = temp[i];
			System.out.print(temp[i] + " ");
		}
		temp = null;
		System.out.println();
	}
}
